package sysu.el.graph.undi.algor;

import java.util.ArrayList;

import sysu.el.array.BoolArray;
import sysu.el.array.TagArray;
import sysu.el.array.algors.Sig;
import sysu.el.array.ints.ArrInt;
import sysu.el.array.ints.ArrQueueInt;
import sysu.el.graph.undi.UndiGTAdjList;

public class UndiBFSAlgor {
	/* ******************************************************************** */
	/* ************************* Attribute op ***************************** */
	/* ******************************************************************** */
	/**
	 * These two attributes decide the class
	 */
	protected BoolArray tag;
	protected ArrQueueInt queue;
	
	//
	public ArrayList<int[]> ans = new ArrayList<int[]>();
	
	/* ******************************************************************** */
	/* ************************* Constructors ***************************** */
	/* ******************************************************************** */
	public UndiBFSAlgor(int len){
		queue = new ArrQueueInt(len);
		tag = new BoolArray(len);
	}

	/* ******************************************************************** */
	/* ************************* Essential OP ***************************** */
	/* ******************************************************************** */
	// Functor State Parameters
	public int curStartNode;
	protected UndiGTAdjList adjList;
	
	public int[] getQueueNodes(){
		if (queue.getTail() >= 0)
			return queue.toArray();
		else return null;
	}
	
	/**
	 * If you want to get the searched nodes, invoke the getQueueNodes();
	 */
	public void bfs(int startNode, UndiGTAdjList gTAdjList){
		tag.reset();
		bfsLite(startNode, gTAdjList);
	}
	
	/**
	 * @param len Length of the searchHeads
	 * @param searchHeads the array contains the head for the bfs
	 * @param gTAdjList the adjList of the graph
	 */
	public ArrayList<int[]> bfs(int len, int searchHeads[], UndiGTAdjList gTAdjList){
		tag.reset();
		ans.clear();
		for (int i=0; i != len; i++){
			bfsLite(searchHeads[i], gTAdjList);
			int[] elem = this.getQueueNodes();
			if (elem != null)
				ans.add(elem);
		}
		return ans;
	}

	public ArrayList<int[]> bfs(UndiGTAdjList gTAdjList){
		tag.reset();
		ans.clear();
//		for (int i=gTAdjList.getNodeNum()-1; i>=0; --i){
		int num = gTAdjList.getNodeNum();
		for (int i=0; i != num; ++i){
			bfsLite(i, gTAdjList);
//			System.out.println(this.getQueueNodes());
			int[] elem = this.getQueueNodes();
			if (elem != null)
				ans.add(elem);
		}
		return ans;
	}
	
	public ArrayList<int[]> bfsWithout(int nodeIgnore, UndiGTAdjList gTAdjList){
		tag.reset();
		ans.clear();
		tag.setVisited(nodeIgnore);
		int num = gTAdjList.getNodeNum();
		for (int i=0; i != num; ++i){
			bfsLite(i, gTAdjList);
//			System.out.println(this.getQueueNodes());
			int[] elem = this.getQueueNodes();
			if (elem != null)
				ans.add(elem);
		}
		return ans;
	}
	
	public ArrayList<int[]> bfsWithout(int nodeIgnore, int len, int searchHeads[], UndiGTAdjList gTAdjList){
		tag.reset();
		tag.setVisited(nodeIgnore);
		ans.clear();
		int num = gTAdjList.getNodeNum();
		for (int i=0; i != num; ++i){
			bfsLite(i, gTAdjList);
//			System.out.println(i + "\t" +this.getQueueNodes());
//			System.out.println(i + "\t" +this.tag.toString());
//			int [] a = this.queue.toArray();
//			if (a.length != 0)
//			System.out.println(i + "\t" + Sig.mkString(a, ","));
			
			int[] elem = this.getQueueNodes();
			if (elem != null)
				ans.add(elem);
		}
		return ans;
	}

	/* ******************************************************************** */
	/* ************************* Auxiliary OP ***************************** */
	/* ******************************************************************** */

	private void addToBFSQueue(int node){
		if (tag.isUnvisited(node)){
			queue.add(node);
			tag.setVisited(node);
		}
	}

	/**
	 * Override this function, but don't forget to invoke super(), 
	 * unless you got different ideas.
	 */
	public void setup(){
		queue.reset();
		this.addToBFSQueue(this.curStartNode);
	}
	
	public void bfsLite(int startNode, UndiGTAdjList gTAdjList){
		this.curStartNode = startNode;
		this.adjList = gTAdjList;
		this.bfsLite();
	}
	
	public void bfsLite(){
		this.setup();
		while (queue.isNotEmpty()){
			int h = queue.forward();
			int list[] = this.adjList.getList(h);
			int num = this.adjList.getDegree(h);
			for (int i=0; i != num; ++i){
				int elem = list[i];
				this.addToBFSQueue(elem);
			}
		} // End While
	}
}
